package com.zz.sort;

import java.util.Arrays;

public class SortZZ {

    /**
     * 冒泡排序1(优化)
     *
     * @param arr
     */
    public static void maoSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    public static void maoQSort(int[] arr) {
        int temp;
        int lastIndex = arr.length;
        int tempIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 1; j < lastIndex; j++) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = false;
                    tempIndex = j;
                }
            }
            lastIndex = tempIndex;
            if (flag) {
                break;
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public static void xuanSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insert = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > insert) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = insert;
        }
    }

    /**
     * 插入排序优化（二分的方式）
     *
     * @param arr
     */
    public static void insertQSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insert = arr[i];
            int j = i - 1;

            arr[j + 1] = insert;
        }
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quitSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int low = left;
        int row = right;
        int temp = arr[left];
        while (left < right) {
            while (left != right) {
                if (arr[right] < temp) {
                    arr[left] = arr[right];
                    break;
                }
                right--;
            }

            while (left != right) {
                if (arr[left] > temp) {
                    arr[right] = arr[left];
                    break;
                }
                left++;
            }
        }
        arr[left] = temp;
        //每次结束打印数组
//        System.out.println(Arrays.toString(arr));
        //重合之后,先看左侧
        right = right != 0 ? right - 1 : right;
        quitSort(arr, low, right);
        //之后再看右侧
        left = left != arr.length - 1 ? left + 1 : left;
        quitSort(arr, left, row);
    }

    /**
     * 计数排序
     *
     * @param arr
     */
    public static void countSort(int[] arr) {
        //计算数组的最大值
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        if (max < 0) {
            //按道理，这里应该抛出异常处理
            return;
        }
        int[] countArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }
        //重新构建数组
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                arr[index++] = i;
            }
        }
    }

    /**
     * 计数排序改良版
     *
     * @param arr
     */
    public static void countQSort(int[] arr) {
        //计算数组的最大值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }

        int[] countArr = new int[max - min + 1];
        boolean flag = true;
        //先给countArr的内容初始化
        for (int i = 0; i < countArr.length; i++) {
            countArr[i] = min + i;
        }
        //填充countArr的内容
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i] - min - i; j++) {
                arr[index++] = min + i;
            }
        }
    }

    /**
     * 归并排序递归版
     * @param arr
     */
    public static void megerSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }
        meger(arr, 0, arr.length - 1);
    }

    public static void meger(int[] arr, int left, int right) {
        int mid = (left + right) >> 1;
        if (left < right) {
            meger(arr, left, mid);
            meger(arr, mid + 1, right);

            megerSwap(arr, left, mid, right);
        }
    }

    public static void megerSwap(int[] arr, int left, int mid, int right) {
        int[] newArr = new int[arr.length];
        int i = left, j = mid + 1, index = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                newArr[index++] = arr[i++];
            } else {
                newArr[index++] = arr[j++];
            }
        }

        //处理左半边多余的数据
        while (i <= mid) {
            newArr[index++] = arr[i++];
        }
        //处理右半边多余的数据
        while (j <= right) {
            newArr[index++] = arr[j++];
        }

        //把临时数组中的数据重新放入原数组
        for (int k = 0; k < index; k++) {
            arr[left + k] = newArr[k];
        }
    }

    /**
     * 非递归方法实现
     * @param arr
     */
    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 步长
        int mergeSize = 1;
        while (mergeSize < N) { // log N
            // 当前左组的，第一个位置
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                megerSwap(arr, L, M, R);
                L = R + 1;
            }
            // 防止溢出
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }

}
